Many candidates assume increasing ef at query time always improves recall with only a linear latency cost. What's misleading about that assumption?

The assumption has two parts, and both are misleading. The first part is that recall always improves with ef. In practice, recall vs ef is a concave curve that saturates: on most datasets, recall rises steeply from ef=16 to ef=128, then flattens, and beyond ef=256 the gain is often fractions of a point. The saturation point depends on the intrinsic dimensionality of the data and on how well the graph is built (m, ef_construct). Once the traversal has visited the entire relevant region of the graph, more ef does not find anything new. The second part is that latency grows linearly with ef. In a compute-bound regime, the number of distance computations does scale roughly linearly with ef, so latency grows roughly linearly. But in a memory-bound or cache-bound regime, higher ef means more nodes visited, which means more cache misses, which means latency grows faster than linearly. And when a filter is present, the picture changes: the filter-aware traversal has to explore more of the graph to find enough matching points, so the effective cost grows with the filter's selectivity. At very high ef with a selective filter, the traversal can approach a full scan, and the latency curve becomes steep.

The mechanism that produces the saturation is that HNSW is a greedy best-first search over a graph. The search terminates when the candidate list is exhausted - that is, when no unexplored neighbor is closer than the current worst result. Increasing ef makes the candidate list larger, which means the search explores more of the graph before terminating. But the graph has a finite number of nodes, and the relevant region for a query is bounded. Once the search has explored the entire connected region around the query, more ef only adds nodes that are farther away and do not change the top-k. This is why recall saturates. The mechanism that produces the non-linear latency is that higher ef visits more nodes, and each node visit has a cache cost. If the graph fits in cache, the cost per visit is low and latency grows roughly linearly. If the graph does not fit, each visit is more likely to miss the cache and pay a memory latency, so the cost per visit grows with the working set. The interaction with filters is that the filter reduces the fraction of visited nodes that are candidates, so the search must visit more nodes to find the same number of results, which amplifies both effects.

The trade-off is between recall and latency, and the misconception is that the trade-off is uniform. It is not: the marginal cost of recall increases as you push toward high recall. This is why the right strategy is to find the knee of the curve and set the default ef there, then use higher ef only for specific queries that need it. The common mistakes are: (1) setting ef very high by default to maximize recall, which costs latency on every query for a small gain; (2) assuming the latency cost is linear and planning capacity accordingly, then discovering the tail is worse than expected; (3) ignoring the filter interaction, so filtered queries with high ef have much worse latency than unfiltered ones; (4) not measuring the recall-vs-ef curve on the actual data, so the knee is unknown; (5) treating ef as the only recall lever when m and ef_construct change the curve itself. Version note: the exact shape of the recall-vs-ef and latency-vs-ef curves depends on the Qdrant version's implementation of filter-aware traversal and on the storage layout (in-memory vs on-disk, quantized vs full precision). Re-measure after upgrades.

Version-dependent: the recall-vs-ef and latency-vs-ef curves depend on the Qdrant version's filter-aware traversal, the storage layout, and the quantization settings. Measure on your version and with your data rather than assuming a shape from a blog post.